#pragma once
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <cassert>
#include <sys/cdefs.h>
#include <tuple>
#include <type_traits>
#include "elemtag.hpp"
#include "memory_cpp.hpp"
// #define __always_inline __attribute__((always_inline)) inline
typedef unsigned int hashval_t;
struct prime_ent {
  hashval_t prime;
  hashval_t inv;
  hashval_t inv_m2; /* inverse of prime-2 */
  hashval_t shift;
};

static struct prime_ent const prime_tab[] = {
    {7, 0x24924925, 0x9999999b, 2},
    {13, 0x3b13b13c, 0x745d1747, 3},
    {31, 0x08421085, 0x1a7b9612, 4},
    {61, 0x0c9714fc, 0x15b1e5f8, 5},
    {127, 0x02040811, 0x0624dd30, 6},
    {251, 0x05197f7e, 0x073260a5, 7},
    {509, 0x01824366, 0x02864fc8, 8},
    {1021, 0x00c0906d, 0x014191f7, 9},
    {2039, 0x0121456f, 0x0161e69e, 10},
    {4093, 0x00300902, 0x00501908, 11},
    {8191, 0x00080041, 0x00180241, 12},
    {16381, 0x000c0091, 0x00140191, 13},
    {32749, 0x002605a5, 0x002a06e6, 14},
    {65521, 0x000f00e2, 0x00110122, 15},
    {131071, 0x00008001, 0x00018003, 16},
    {262139, 0x00014002, 0x0001c004, 17},
    {524287, 0x00002001, 0x00006001, 18},
    {1048573, 0x00003001, 0x00005001, 19},
    {2097143, 0x00004801, 0x00005801, 20},
    {4194301, 0x00000c01, 0x00001401, 21},
    {8388593, 0x00001e01, 0x00002201, 22},
    {16777213, 0x00000301, 0x00000501, 23},
    {33554393, 0x00001381, 0x00001481, 24},
    {67108859, 0x00000141, 0x000001c1, 25},
    {134217689, 0x000004e1, 0x00000521, 26},
    {268435399, 0x00000391, 0x000003b1, 27},
    {536870909, 0x00000019, 0x00000029, 28},
    {1073741789, 0x0000008d, 0x00000095, 29},
    {2147483647, 0x00000003, 0x00000007, 30},
    /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
    {0xfffffffb, 0x00000006, 0x00000008, 31}};

__always_inline hashval_t
htab_hash_string(const char *s) {
  hashval_t ret = 0;
  const char *p;
  for (p = s; *p; p++) {
    ret = ret * 67 + ((unsigned)(*p) - 113);
  }
  return ret;
}

#define htab_mix(a, b, c)                  \
  {                                   \
    a -= b;                           \
    a -= c;                           \
    a ^= (c >> 13);                   \
    b -= c;                           \
    b -= a;                           \
    b ^= (a << 8);                    \
    c -= a;                           \
    c -= b;                           \
    c ^= ((b & 0xffffffff) >> 13);    \
    a -= b;                           \
    a -= c;                           \
    a ^= ((c & 0xffffffff) >> 12);    \
    b -= c;                           \
    b -= a;                           \
    b = (b ^ (a << 16)) & 0xffffffff; \
    c -= a;                           \
    c -= b;                           \
    c = (c ^ (b >> 5)) & 0xffffffff;  \
    a -= b;                           \
    a -= c;                           \
    a = (a ^ (c >> 3)) & 0xffffffff;  \
    b -= c;                           \
    b -= a;                           \
    b = (b ^ (a << 10)) & 0xffffffff; \
    c -= a;                           \
    c -= b;                           \
    c = (c ^ (b >> 15)) & 0xffffffff; \
  }

static hashval_t
htab_hash_i64(long p) {
  unsigned a, b, c;
  a = b = 0x9e3779b9;
  a += (hashval_t)(p >> (32));
  b += (hashval_t)(p & -1);
  c = 0x42135234;
  htab_mix(a, b, c);
  return c;
}
struct cchar_key {
  typedef const char *key_type;
  static void copy(const char *&dst, const char * const &src) {
    dst = strdup(src);
  }
  static hashval_t hash(const char * const &key) {
    return htab_hash_string(key);
  }
  static bool equal(const char * const &k1, const char * const &k2) {
    return strcmp(k1, k2) == 0;
  }
};
struct tag_key {
  typedef long key_type;
  static void copy(long &dst, const long &src) {
    dst = src;
  }
  static hashval_t hash(const long &key) {
    return htab_hash_i64(key);
  }
  static bool equal(const long &key1, const long &key2) {
    return key1 == key2;
  }
};
namespace esmd{
template <typename TKC, typename TV>
struct htab{
  typedef typename TKC::key_type TK;
  struct item_t {
    TK key;
    TV val;
    int status;
  };
  item_t *slots;
  unsigned int cap, cnt;
  unsigned long nquery, nscan;
  const prime_ent *prime_cur;
  memrec_t *rec;
  enum {
    STAT_EMPTY,STAT_DELETED,STAT_USED
  };
  __always_inline htab(memrec_t *rec, int initial_size=32) : rec(rec) {
    prime_cur = prime_tab + 2;
    while (prime_cur->prime * 3 < initial_size * 4) prime_cur ++;
    nquery = 0;
    nscan = 0;
    cap = prime_cur->prime;
    cnt = 0;
    slots = esmd::allocate<item_t>(cap, rec);
    for (int i = 0; i < cap; i ++)
      slots[i].status = STAT_EMPTY;
  }
  __always_inline htab(int initial_size, memrec_t *rec) : htab(rec, initial_size){};
  __always_inline htab(int initial_size, const char *name) : htab(get_memrec(name), initial_size){};
  __always_inline htab(const char *name, int initial_size = 32) : htab(get_memrec(name), initial_size){};
  ~htab(){
    esmd::deallocate(slots);
  }
  __always_inline bool grow(){
    if (cap * 3 < cnt * 4) {
      prime_cur ++;
      item_t *old_slots = slots;
      item_t *old_top = slots + cap;
      cap = prime_cur->prime;
      slots = esmd::allocate<item_t>(cap, rec);
      for (int i = 0; i < cap; i ++)
        slots[i].status = STAT_EMPTY;
      for (item_t *slot = old_slots; slot != old_top; slot ++) {
        if (slot->status != STAT_EMPTY && slot->status != STAT_DELETED) {
          hashval_t hv = TKC::hash(slot->key);
          item_t *new_slot = find_slot_hash(slot->key, hv);
          new_slot->key = slot->key;
          new_slot->val = slot->val;
          new_slot->status = STAT_USED;
        }
      }
      esmd::deallocate(old_slots);
      return true;
    }
    return false;
  }
  __always_inline item_t *find_slot_hash(const TK &key, hashval_t hv) {
    item_t *avail = NULL;
    hashval_t index = hv % prime_cur->prime;
    item_t *slot = slots + index;
    if (slot->status == STAT_EMPTY) {
      return slot;
    } else if (slot->status == STAT_DELETED) {
      avail = slot;
    } else if (TKC::equal(slot->key, key)) {
      return slot;
    }
    hashval_t hash2 = 1 + hv % (prime_cur - 2)->prime;
    while (1) {
      index += hash2;
      if (index >= cap)
        index -= cap;
      slot = slots + index;
      if (slot->status == STAT_EMPTY) {
        return avail != NULL ? avail : slot;
      } else if (slot->status == STAT_DELETED) {
        avail = avail == avail ? avail : slot;
      } else if (TKC::equal(slot->key, key)){
        return slot;
      }
    }
  }
  __always_inline TV &operator[](const TK &key) {
    item_t *item = find_slot_hash(key, TKC::hash(key));
    if (item->status != STAT_USED){
      if (grow()) item = find_slot_hash(key, TKC::hash(key));
      TKC::copy(item->key, key);
      item->status = STAT_USED;
      cnt ++;
    }
    return item->val;
  }
  __always_inline TV get(const TK &key, const TV &def) {
    item_t *item = find_slot_hash(key, TKC::hash(key));
    if (item->status != STAT_USED){
      return def;
    }
    return item->val;
  }
  __always_inline TV &setdefault(const TK &key, const TV &def) {
    item_t *item = find_slot_hash(key, TKC::hash(key));
    if (item->status != STAT_USED){
      if (grow()) item = find_slot_hash(key, TKC::hash(key));

      TKC::copy(item->key, key);
      item->val = def;
      item->status = STAT_USED;
      cnt ++;
    }
    return item->val;
  }
  __always_inline TV &setdefault(const TK &key, TV (*defgen)()) {
    item_t *item = find_slot_hash(key, TKC::hash(key));
    if (item->status != STAT_USED){
      if (grow()) item = find_slot_hash(key, TKC::hash(key));

      TKC::copy(item->key, key);
      item->val = defgen();
      item->status = STAT_USED;
      cnt ++;
    }
    return item->val;
  }
  __always_inline void remove(const TK &key) {
    item_t *item = find_slot_hash(key, TKC::hash(key));
    if (item->status == STAT_USED){
      item->status = STAT_DELETED;
      cnt --;
    }
  }
  __always_inline bool contains(const TK &key) {
    item_t *item = find_slot_hash(key, TKC::hash(key));
    return item->status == STAT_USED;
  }
  __always_inline int size(){
    return cnt;
  }
  struct iterator{
    item_t *slot, *limit;
    // iterator &operator++(int n){
    //   while (slot < limit && slot->status != STAT_USED) slot ++;
    //   return *this;
    // }
    void ensure(){
      while (slot < limit && slot->status != STAT_USED) slot ++;
    }
    iterator &operator++(){
      slot ++;
      ensure();
      return *this;
    }

    bool operator ==(const iterator &o){
      return slot == o.slot;
    }
    bool operator !=(const iterator &o) {
      return slot != o.slot;
    }
    item_t &operator *(){
      return *slot;
    }
  };
  __always_inline iterator begin(){
    iterator a = {slots, slots + cap};
    a.ensure();
    return a;
  }
  __always_inline iterator end(){
    return iterator{slots + cap, slots + cap};
  }
  // struct iterator{
  //   int idx;
  //   htab *tab;
  //   iterator(htab *tab, int idx) : tab(tab), idx(idx) {}
  //   item_t &operator *(){
  //     return tab->slots[idx];
  //   }
  //   iterator &operator ++(int n){
  //     do {
  //       idx ++;
  //     } while (idx < tab->cap && tab->slots[idx].status != STAT_USED);
  //     return *this;
  //   }
  //   bool operator ==(const iterator &other) {
  //     return tab == other.tab && idx == other.idx;
  //   }
  //   bool operator !=(const iterator &other) {
  //     return tab != other.tab || idx != other.idx;
  //   }
  // };
  // __always_inline iterator begin(){
  //   iterator ret(this, 0);
  //   if (slots[ret.idx].status != STAT_USED) ret ++;
  //   return ret;
  // }
  // __always_inline iterator end() {
  //   return iterator(this, cap);
  // }
  
};
}
